package com.it.od.binary;

import java.util.Arrays;

/**
 * @author: liminghui
 * @date: 2024/3/9 9:25
 * @version: 1.0
 * @description:
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 10};
        int x = 1;

        int idx = Arrays.binarySearch(arr, x);
        int res2 = binarySearch3(arr, x);
        System.out.println(res2);
    }

    // 等于x
    public static int binarySearch1(int[] arr, int x) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] > x) {
                high = mid - 1;
            } else if (arr[mid] < x) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -(low + 1);
    }

    // 大于等于x
    public static int binarySearch2(int[] arr, int x) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] >= x) {
                if (mid == 0 || arr[mid - 1] < x) {
                    return mid;
                }
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 第一个小于等于x
    public static int binarySearch3(int[] arr, int x) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] <= x) {
                if (mid == arr.length - 1 || arr[mid + 1] > x) {
                    return mid;
                }
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
